//1.前缀和 - 寻找数组的中心下标
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //预处理前缀和、后缀和数组
        int n = nums.size();
        int f[10010] = {0}, g[10010] = {0};
        for(int i = 1; i < n; i++)
            f[i] = f[i-1] + nums[i-1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i+1] + nums[i+1];
        //使用前缀和、后缀和数组
        for(int i = 0; i < n; i++)
            if(f[i] == g[i]) return i;
        return -1;
    }
};

//2.除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //f[i]表示[0, i - 1]区间的乘积, g[i]表示[n - 1, i + 1]区间的乘积
        vector<int> ret;
        int n = nums.size();
        int f[100010] = {0}, g[100010] = {0};
        f[0] = g[n - 1] = 1;
        for(int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];
        for(int i = 0; i < n; i++)
            ret.push_back(f[i] * g[i]);
        return ret;
    }
};